package com.hxm.demo.test1;


import java.util.Arrays;
import java.util.HashSet;

/**
 * @author huangxiaoming
 * @description
 * @date 2022/5/19 22:19
 */
public class TwoSum {

    public static void main(String[] args) {
        int[] numbers = {1, 7, 9, 11};
        int target = 16;
        int[] ints = twoSum(numbers, target);
        System.out.println(ints[0] + "<------>" + ints[1]);

        System.out.println(reverString("leetcode"));

        System.out.println(validPalindrome("anssa"));
    }

    /**
     * 题目描述：在有序数组中找出两个数，使它们的和为 target。
     * <p>
     * 使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
     * <p>
     * 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
     * 如果 sum > target，移动较大的元素，使 sum 变小一些；
     * 如果 sum < target，移动较小的元素，使 sum 变大一些。
     * 数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。
     *
     * @param numbers
     * @param target
     * @return
     */
    private static int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return null;
        }
        int i = 0;
        int j = numbers.length - 1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum > target) {
                j--;
            } else if (sum < target) {
                i++;
            } else {
                return new int[]{i++, j--};
            }
        }
        return null;
    }

    /**
     * 题目描述：判断一个非负整数是否为两个整数的平方和。
     * <p>
     * 可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。
     * <p>
     * 本题和 167. Two Sum II - Input array is sorted 类似，只有一个明显区别：一个是和为 target，一个是平方和为 target。本题同样可以使用双指针得到两个数，使其平方和为 target。
     * <p>
     * 本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。
     * <p>
     * 因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。
     *
     * @param target
     * @return
     */
    private static boolean judgeSquareSum(int target) {
        if (target < 0) {
            return false;
        }
        int i = 0, j = (int) Math.sqrt(target);
        while (i < j) {
            int sum = i * i + j * j;
            if (sum < target) {
                i++;
            } else if (sum > target) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }

    private final static HashSet<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

    /**
     * 题目描述：可以删除一个字符，判断是否能构成回文字符串。
     * <p>
     * 所谓的回文字符串，是指具有左右对称特点的字符串，例如 "abcba" 就是一个回文字符串。
     * <p>
     * 使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串才是具有左右对称性质的回文字符串。
     * <p>
     * <p>
     * 本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。
     * <p>
     * 在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。
     * <p>
     * 在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。
     *
     * @param target
     * @return
     */
    private static String reverString(String target) {
        if (target == null) {
            return null;
        }
        int i = 0;
        int j = target.length() - 1;
        char[] chars = target.toCharArray();
        while (i < j) {
            char ci = target.charAt(i);
            char cj = target.charAt(j);
            if (!vowels.contains(ci)) {
                i++;
            } else if (!vowels.contains(cj)) {
                j--;
            } else {
                chars[i++] = cj;
                chars[j--] = ci;
            }
        }
        return new String(chars);
    }

    /**
     * 题目描述：可以删除一个字符，判断是否能构成回文字符串。
     * <p>
     * 所谓的回文字符串，是指具有左右对称特点的字符串，例如 "abcba" 就是一个回文字符串。
     * <p>
     * 使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串才是具有左右对称性质的回文字符串。
     * <p>
     * <p>
     * 本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。
     * <p>
     * 在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。
     * <p>
     * 在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。
     *
     * @param s
     * @return
     */
    public static boolean validPalindrome(String s) {
        if (s == null) {
            return false;
        }
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
            }
        }
        return true;
    }

    private static boolean isPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }
}
